#include "mythread.h"
#include <QElapsedTimer>
#include <QDebug>
Generate::Generate(QObject *parent) : QThread(parent)
{

}

void Generate::recvNum(int num)
{
    m_num= num;
}

void Generate::run()
{
    qDebug() << "生成随机数的线程的线程的地址: " << QThread::currentThread();
    QVector<int> list;
    QElapsedTimer time;
    time.start();
    for(int i=0;i<m_num;i++)
    {
        list.push_back(qrand() % 100000);
    }
    int milsec = time.elapsed();
    qDebug() << "生成" << m_num << "个随机数总共用时" << milsec << "毫秒";
    emit sendArray(list);
}

BubbleSort::BubbleSort(QObject *parent) : QThread(parent)
{

}

void BubbleSort::recvArray(QVector<int> list)
{
    m_list = list;
}

void BubbleSort::run()
{
    qDebug() << "冒泡排序的线程的线程地址： " << QThread::currentThread();
    QVector<int> list;
    int temp;
    QElapsedTimer time;
    for(int i=0;i<m_list.size();++i)
    {
        for(int j=0;j<m_list.size()-i-1;++j)
        {
            if(m_list[j] > m_list[j+1])
            {
                temp = m_list[j];
                m_list[j] = m_list[j+1];
                m_list[j+1] = temp;
            }
        }
    }
    int milsec = time.elapsed();
    qDebug() << "冒泡排序用时" <<  milsec << "毫秒";
    emit finish(m_list);
}

QuickSort::QuickSort(QObject *parent) : QThread(parent)
{

}

void QuickSort::recvArray(QVector<int> list)
{
    m_list = list;
}

void QuickSort::run()
{
    qDebug() << "快速排序的线程的线程地址： " << QThread::currentThread();
    QElapsedTimer time;
    time.start();
    quicksort(m_list,0,m_list.size()-1);
    int milsec = time.elapsed();
    qDebug() << "快速排序用时" <<  milsec << "毫秒";
    emit finish(m_list);
}

// 快速排序的分区函数
int QuickSort::partition(QVector<int>& arr, int low, int high)
{
    int pivot = arr[high];    // 选择最后一个元素作为基准
    int i = (low - 1);        // 小于基准的元素的最后索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++;    // 增加小于基准的元素的索引
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void QuickSort::quicksort(QVector<int>& arr, int low, int high)
{
    if (low < high) {
        // pi 是分区后基准的索引
        int pi = partition(arr, low, high);

        // 分别对基准前后的子数组进行快速排序
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

